Routers and multi-layer switches in packet-switched networks transmit frames between ingress ports and egress ports with different levels of class of service (CoS). CoS generally refers to the preferential treatment with which some flows are given access to system resources including access to output ports and switch fabric for example. To service the different flows competing for the same port for example, the flows are generally segregated into a plurality of queues, each queue being associated with a different priority level. A queue scheduler is then employed to fairly regulate distribution of the frames from the queues in a manner that gives precedence to the higher priority queues without starving the lower priority queues.
One approach to scheduling queue output is referred to as deficit round robin (DRR). In this approach, the scheduler allocates credits representing units of bandwidth to each of the queues. The credits are then spent as frames are distributed from the queues. If the available credit is less than the credit required to distribute the frame, or otherwise insufficient, the queue may be passed over and the next lower priority queue serviced. At the expiration of a predefined refresh interval, the scheduler re-allocates or otherwise initializes the credits for each of the plurality of queues. The refresh interval on an interface operating at T1 speed is approximately 100 milliseconds while, in comparison, an interface operating at one Gigabit per second is approximately 100 microsecond.
While the DRR scheduling method is effective at fairly allocating output bandwidth, it requires that a clock be maintained and a refresh interval monitored for periodic credit assignments. Unfortunately, the clock and the refresh interval consume computational resources including a significant number of clock cycles on the processor implementing the scheduling method. In many cases, the processor is a specialized network processor also responsible for other tasks including classification and forwarding decisions, for example. In an age when network wire speeds have surpassed one gigabit per second and higher, the computational resources necessary to support standard DRR are unduly burdensome. There is therefore a need for a scheduling mechanism that obviates the need to maintain a scheduler clock and monitor a refresh interval.